import java.util.ArrayList;
import java.util.List;

/**
 * 22. 括号生成
 */
public class Solution_22 {
    /**
     * 题解：https://leetcode-cn.com/problems/generate-parentheses/solution/hui-su-suan-fa-by-liweiwei1419/
     * 
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        dfs("", n, n, ans);
        return ans;
    }

    /**
     * 
     * @param curStr 当前递归得到的结果
     * @param left   左括号还有几个可以使用
     * @param right  右括号还有几个可以使用
     * @param ans    结果集
     */
    private void dfs(String curStr, int left, int right, List<String> ans) {
        // 因为每一次尝试，都使用新的字符串变量，所以无需回溯
        // 在递归终止的时候，直接把它添加到结果集即可，注意与「力扣」第 46 题、第 39 题区分
        if (left == 0 && right == 0) {
            ans.add(curStr);
            return;
        }
        // 剪枝（如图，左括号可以使用的个数严格大于右括号可以使用的个数，才剪枝，注意这个细节）
        if (left > right) {
            return;
        }
        if (left > 0) {
            dfs(curStr + "(", left - 1, right, ans);
        }
        if (right > 0) {
            dfs(curStr + ")", left, right - 1, ans);
        }
    }

    public static void main(String[] args) {
        Solution_22 solution = new Solution_22();
        List<String> ans = solution.generateParenthesis(3);
        System.out.println(ans);
    }
}
